package com.wzh.test.bst;

/**
 * 二叉排序树
 * 1、有一个数组[1,3,5,7,9,2,4,6,8,0]，要求创建一个二叉排序树,并按照中序遍历打印出来
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {0,1,2,3};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            binarySortTree.add(node);
        }
        //binarySortTree.middleOrder();
//        binarySortTree.del(3);
//        binarySortTree.del(0);
//        binarySortTree.del(5);
//        binarySortTree.del(7);
//        binarySortTree.del(1);
        System.out.println("中序遍历打印节点");
        binarySortTree.middleOrder();
    }
}

class BinarySortTree {
    public Node root;

    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
            return;
        }
        Node addParentNode = this.root.add(node);
    }

    public void del(int value) {
        if (root == null) {
            return;
        }
        //首先找到要删除的节点
        Node delNode = root.searchNode(value);
        if(delNode == null){
            return;
        }

        Node newRoot = root;

        if(delNode.left == null && delNode.right == null){
            //如果删除的是叶子节点
            if(delNode != root) {
                //找到父节点
                Node parentNode = root.getParentNode(delNode);
                if (parentNode.left == delNode) {
                    parentNode.left = null;
                } else {
                    parentNode.right = null;
                }
            }else{
                newRoot = null;
            }

        }else if(delNode.left != null && delNode.right == null){
            //如果删除的是非叶子节点，并且只有左子树
            if(delNode != root) {
                Node parentNode = root.getParentNode(delNode);
                parentNode.left = delNode.left;
            }else{
                newRoot= root.left;
            }

        }else if(delNode.left == null && delNode.right != null){
            //如果删除的是非叶子节点，并且只有右子树
            if(delNode != root) {
                Node parentNode = root.getParentNode(delNode);
                parentNode.right = delNode.right;
            }else{
                newRoot = root.right;
            }
        }else{
            //如果删除的是非叶子节点，并且有左右子树
            int balanceFactor = root.getBalnceFactor();
            if(balanceFactor > 0){
                //说明右侧树高,获取右侧树的最小节点
                Node rightMinNode = getRightMinNode(delNode);
                Node rightMinNodeParent = root.getParentNode(rightMinNode);
                rightMinNodeParent.left = null;
                rightMinNode.left = delNode.left;
                if(delNode != root) {
                    Node delNodeParent = root.getParentNode(delNode);
                    delNodeParent.right = rightMinNode;
                } else{
                    newRoot = rightMinNode;
                }

            }else{
                //说明右侧树高,获取左侧树的最大节点

                Node leftMaxNode = getLeftMaxNode(delNode);
                Node leftMaxNodeParent = root.getParentNode(leftMaxNode);
                leftMaxNodeParent.right = null;
                leftMaxNode.right = delNode.right;

                if(delNode != root) {
                    Node delNodeParent = root.getParentNode(delNode);
                    delNodeParent.left = leftMaxNode;
                }else{
                    newRoot = leftMaxNode;
                }
            }
        }

        this.root = newRoot;

    }

    public void middleOrder() {
        if (this.root != null) {
            this.root.middleOrder();
        }else{
            System.out.println("没有数据了");
        }
    }

    private Node getRightMinNode(Node node) {
        if (node.right == null) {
            return null;
        }
        return node.right.getRightMinNode();
    }

    private Node getLeftMaxNode(Node node) {
        if (node.left == null) {
            return null;
        }
        return node.left.getLeftMaxNode();
    }


}

class Node {
    public int value;
    public Node left;
    public Node right;

    /**
     * 前序遍历查找节点
     *
     * @param value
     */
    public Node searchNode(int value) {
        if (this.value == value) {
            return this;
        } else if (this.value > value) {
            if (this.left == null) {
                return null;
            } else {
                return this.left.searchNode(value);
            }
        } else {
            if (this.right == null) {
                return null;
            } else {
                return this.right.searchNode(value);
            }
        }
    }

    public void del(Node parentNode, int value) {
        if (this.value == value) {
            //找到右边最小的节点
            //this.getMinRightNode();
        }
    }

    public Node getRightMinNode() {
        if (this.left == null) {
            return this;
        } else {
            return this.left.getRightMinNode();
        }
    }

    public Node getLeftMaxNode() {
        if (this.right == null) {
            return this;
        } else {
            return this.right.getLeftMaxNode();
        }
    }


    public int getBalnceFactor() {
        return this.getRHeight() - this.getLHeight();
    }

    public int getLHeight() {
        return this.left == null ? 0 : this.left.getLHeight() + 1;
    }

    public int getRHeight() {
        return this.right == null ? 0 : this.right.getRHeight() + 1;
    }

    public Node(int value) {
        this.value = value;
    }

    public void middleOrder() {
        if (this.left != null) {
            this.left.middleOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.middleOrder();
        }
    }

    public Node add(Node node) {
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
                return this;
            } else {
                return this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
                return this;
            } else {
                return this.right.add(node);
            }
        }
    }

    public Node getParentNode(Node node) {
        if (this.left == node || this.right == node) {
            return this;
        } else if (this.value > node.value) {
            return this.left.getParentNode(node);
        } else {
            return this.right.getParentNode(node);
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
